package leetcode_core.sort;

import org.junit.Test;

import java.util.Arrays;

public class BinarySearch {
    //基础二分法,定义搜索区间为[left,right]
    public static boolean isExist(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int left = 0, right = arr.length;
        // [left,right]何时不存在?当[1,1]这种情况是可以接受的
        // 但是[2,1]这种情况是不可以接受的
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == num) {
                return true;
            } else if (arr[mid] < num) {
                //这要做的是区间的缩减
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
    //arr有序,>=num最左的位置,找不到就返回-1
    public static int mostLeftNum(int[] arr,int num){
        if(arr == null || arr.length == 0){
            return -1;
        }
        int mostLeft = -1;//中途发生的最早的左边界下标
        int left = 0,right = arr.length-1;
        while (left <= right){
            //mostLeft有可能会更新
            int mid = left + (right-left)/2;
            if(arr[mid] >= num){//符合题目条件的数
                mostLeft = mid;//这时候就更新,然后包含mid和他右边的区间都砍掉
                right = mid-1;
            }else{
                //这时候不更新,把左边连同它自己砍掉
                left = mid+1;
            }
        }
        return mostLeft;
    }

    public static int mostRight(int[] arr,int num){
        int mostRight = -1;
        if(arr == null || arr.length == 0){
            return mostRight;
        }
        int left = 0,right = arr.length-1;
        while (left <= right){
            int mid = left + (right - left)/2;
            if(mid <= num){
                mostRight = mid;
                //arr[mid] <= mid,这时候想要找到更右的,连同它自己和左边的全部干掉
                left = mid+1;
            }else{
                //这时候还没有找到比它小的,连同自己和它右边全部干掉
                right = mid-1;
            }
        }
        return mostRight;
    }

    public static int[] randomArray(int maxLen,int maxValue){
        int len = (int)(Math.random());
        int[] arr = new int[len];
        if(len>0){
            arr[0] = (int)(Math.random()*maxValue);
            for(int i = 1;i<len;i++){
                do {
                    arr[i] = (int)(Math.random()*maxValue);
                }while (arr[i] == arr[i-1]);
            }
        }
        return arr;
    }


    public static int mostSmallNum(int[] arr){
        if(arr == null || arr.length == 0){
            return -1;
        }
        if(arr.length == 1){
            return 0;
        }
        //边界情况
        if(arr[0]<arr[1]){
            return 0;
        }
        if(arr[arr.length-1] < arr[arr.length-2] ){
            return arr.length-1;
        }
        int left = 1,right =arr.length-2;
        int ans = -1;
        while (left <= right){
            int mid = left+(right-left)/2;
            //由于涉及到mid-1和mid+1,这里一定要慎重讨论
            if(arr[mid] < arr[mid-1] && arr[mid] <arr[mid+1]){
                ans = mid;
                break;
            }
            if(arr[mid] > arr[mid-1]){
                right = mid-1;
                continue;
            }
            if(arr[mid] > arr[mid+1]){
                left = mid+1;
                continue;
            }
        }
        return ans;

    }

    /**
     * 对数器
     * @param arr
     * @param num
     * @return
     */
    public static boolean isMin(int[] arr,int num){
        if(arr.length == 0){
            return num == -1? true:false;
        }
        int left = num-1;
        int right = num+1;
        boolean leftBigger = left >= 0?arr[left]>arr[num]:true;
        boolean rightBigger = right<=arr.length-1?arr[right]>arr[num]:true;
        return leftBigger&&rightBigger;
    }

    public static void main(String[] args) {
        int testTimes = 1;
        int maxLen = 1000000;
        int maxValue = 1000;
        System.out.println("测试开始");
        for(int i = 0;i<testTimes;i++){
            int[] ints = randomArray(maxLen, maxValue);
            ints = new int[]{4,3,5,4,3,2,1};
            int ans = mostSmallNum(ints);
            if(!isMin(ints,ans)){
                System.out.println("出错了:"+Arrays.toString(ints)+" "+ans);
                break;
            }
        }
        System.out.println("测试结束");
    }


}
